190D - Non-Secret Cypher - CodeForces Solution

two pointers *1900

Please click on ads to support us..

Python Code: 


def subarrays_with_k(nums, k):
    count = {}
    res = 0

    def add(x):
        count[nums[x]] = 1 + count.get(nums[x], 0)

    def good(x):
        return nums[x] in count and count[nums[x]] >= k

    def remove(x):
        if count[nums[x]] == 0:
            del count[nums[x]]
        else:
            count[nums[x]] -= 1

    l = 0
    for r in range(len(nums)):
        add(r)
        if good(r):
            while good(r):
                remove(l)
                l += 1
                res += len(nums) - r
    return res

if __name__ == "__main__":
    _, k = list(map(int, input().strip().split()))
    nums = list(map(int, input().strip().split()))
    print(subarrays_with_k(nums, k))

C++ Code: 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<int> b = a;
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());

    for (auto& x: a) x = int(lower_bound(b.begin(), b.end(), x) - b.begin());

    vector<int> cnt(b.size());

    long long ans = 0;
    bool ok = false;
    for (int i = 0, j = 0; i < n; ++i) {
        cnt[a[i]] += 1;
        while (j < i && (cnt[a[i]] > k || (cnt[a[i]] == k && a[j] != a[i]))) {
            cnt[a[j]] -= 1;
            j += 1;
        }

        if (cnt[a[i]] >= k) ok = true;
        if (ok) ans += j + 1;
    }

    cout << ans << "\n";

    return 0;
}


Comments

Submit
0 Comments
More Questions

1035. Uncrossed Lines
328. Odd Even Linked List
1219. Path with Maximum Gold
1268. Search Suggestions System
841. Keys and Rooms
152. Maximum Product Subarray
337. House Robber III
869. Reordered Power of 2
1593C - Save More Mice
1217. Minimum Cost to Move Chips to The Same Position
347. Top K Frequent Elements
1503. Last Moment Before All Ants Fall Out of a Plank
430. Flatten a Multilevel Doubly Linked List
1290. Convert Binary Number in a Linked List to Integer
1525. Number of Good Ways to Split a String
72. Edit Distance
563. Binary Tree Tilt
1306. Jump Game III
236. Lowest Common Ancestor of a Binary Tree
790. Domino and Tromino Tiling
878. Nth Magical Number
2099. Find Subsequence of Length K With the Largest Sum
1608A - Find Array
416. Partition Equal Subset Sum
1446. Consecutive Characters
1618A - Polycarp and Sums of Subsequences
1618B - Missing Bigram
938. Range Sum of BST
147. Insertion Sort List
310. Minimum Height Trees